/*
Date:20210417 10:36pm
key:用栈模拟一遍，将所有无法匹配的括号的位置全部置1
例如: "()(()"的mark为[0, 0, 1, 0, 0]
再例如: ")()((())"的mark为[1, 0, 0, 1, 0, 0, 0, 0]
经过这样的处理后, 此题就变成了寻找最长的连续的0的长度
*/class Solution {
public:
//dp[i]指，i及以前的最长连续有效字串
    int longestValidParentheses(string s) {
        if(s.size()==0)
        {
            return 0;
        }
        //初始化标记数组
        bool *flag=new bool[s.size()];
        for(int i=0;i<s.size();i++)
        {
            flag[i]=0;
        }
        stack<int>I;
        //弹出再计数
        for(int i=0;i<s.size();i++)
        {
            if(I.empty())
            {
                //记录没机会入栈的下标
                if(s[i]==')')
                {
                    flag[i]=1;
                }
                else
                {
                    I.push(i);
                }
                
            }
            else
            {
                if(s[i]==')')
                {
                    //if(s[S.top()]=='(')
                    {
                        I.pop();
                    }
                }
                else
                {
                    I.push(i);
                }
            }

        }
        //记录没机会出栈的下标
        while(!I.empty())
        {
            flag[I.top()]=1;
            I.pop();
        }
        int max=0;
        int count=0;
        int *dp=new int[s.size()];
        for(int i=0;i<s.size();i++)
        {
            cout<<flag[i]<<" ";
            if(flag[i]==1)
            {

                count=0;
            }
            else
            {
                count++;
                if(count>max)
                {
                    max=count;
                    
                }
            }
        }
        return max;
    }
};